

# 474.一和零


def findMaxForm(strs, m, n):
    """
    :type strs: List[str]
    :type m: int
    :type n: int
    :rtype: int
    """

    def element(strd):
        zero = 0
        one = 0
        for i in strd:
            if i == "0":
                zero = zero + 1
            elif i == "1":
                one = one + 1
        return zero, one

    dp = [[[None] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs))]
    dp[0][0][0] = 0
    for i in range(1, len(strs)):
        dp[i][0][0] = 0

    for i in range(0, len(strs)):
        for j in range(1, n + 1):
            zero, one = element(strs[i])
            if zero == 0 and one <= j:
                if i != 0:
                    dp[i][0][j] = max(dp[i - 1][0][j], dp[i - 1][0][j - one]+1)
                else:
                    dp[i][0][j] = 1
            else:
                if i==0:
                    dp[i][0][j] = 0
                else:
                    dp[i][0][j] = dp[i-1][0][j]

    for i in range(0, len(strs)):
        for j in range(1, m + 1):
            zero, one = element(strs[i])
            if one == 0 and zero <= j:
                if i != 0:
                    dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - zero][0]+1)
                else:
                    dp[i][j][0] = 1
            else:
                if i==0:
                    dp[i][j][0] = 0
                else:
                    dp[i][j][0] = dp[i-1][j][0]

    for i in range(0, m + 1):
        for j in range(0, n + 1):
            zero, one = element(strs[0])
            if zero <= i and one <= j:
                dp[0][i][j] = 1
            else:
                dp[0][i][j] = 0

    for i in range(1, len(strs)):
        zero, one = element(strs[i])
        for j in range(1, m + 1):
            for k in range(1, n + 1):
                if j >= zero and k >= one:
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - zero][k - one] + 1)
                else:
                    dp[i][j][k] = dp[i - 1][j][k]
    print(dp)
    return dp[len(strs) - 1][m][n]


if __name__ == "__main__":
    strs = ["0","0","1","1"]
    m = 2
    n = 2
    print(findMaxForm(strs,m,n))